#include "headfiles.h"

using namespace std;

static bool createHeap(int *array, int n) {
    if (array == NULL||
        n <= 0) {
        cout << "Invalid arguments!" << endl;
        return false;
    }

    int end = (n - 2) / 2;
    int i, index, l_child, r_child, swap_index;

    for (i = end; i >= 0; i--) {
        index = i;
        while (index < n) {
            l_child = 2 * index + 1;
            r_child = 2 * index + 2;

            swap_index = -1;
            if (l_child < n && array[index] > array[l_child]) {
                swap_index = l_child;
            }

            if (r_child < n && array[index] > array[r_child]) {
                if (array[l_child] > array[r_child]) {
                    swap_index = r_child;
                }
            }

            if (swap_index != -1) {
                int tmp = array[swap_index];
                array[swap_index] = array[index];
                array[index] = tmp;

                index = swap_index;
            }
            else {
                break;
            }
        }
    }

    return true;
}

bool heapSort(int *array, int n) {
    if (array == NULL || 
        n <= 0) {
        cout << "Invalid input arguments!" << endl;
        return false;
    }

    bool ret = createHeap(array, n);
    if (ret == false) {
        return false;
    }

    cout << "Heap elems:" << endl;
    int i;
    for (i = 0; i < n; i++) {
        cout << array[i] << endl;
    }
    cout << endl;

    int last_loc = n - 1;
    int index, l_child, r_child, swap_loc;
    while (last_loc > 0) {
        // Swap the first element with that in loc index
        int tmp = array[last_loc];
        array[last_loc] = array[0];
        array[0] = tmp;

        // heapify the heap with the number of element index
        index = 0;
        while (index < last_loc) {
            l_child = 2 * index + 1;
            r_child = 2 * index + 2;

            swap_loc = -1;
            if (l_child < last_loc && array[index] > array[l_child]) {
                swap_loc = l_child;
            }

            if (r_child < last_loc && array[index] > array[r_child]) {
                if (array[l_child] > array[r_child]) {
                    swap_loc = r_child;
                }
            }

            if (swap_loc != -1) {
                tmp = array[index];
                array[index] = array[swap_loc];
                array[swap_loc] = tmp;

                index = swap_loc;
            }
            else {
                break;
            }
        }

        last_loc--;
    }

    return true;
}

